package com.jhy.review.day02;

import com.jhy.review.day01.Node;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 求第一个汇聚的点就是最低公共祖先
 * 先把所有节点
 * 求两个节点的最低公共祖先
 * 时间复杂度为O（N）
 *
 */
public class LowestCommonAncestor {

    // o1 和 o2 一定是属于head为头的树
    // 返回最低公共祖先
    public static Node lca(Node head, Node o1, Node o2) {
        //  用一个fatherMap 来存放当前节点的父节点  只要记录到了该节点的父节点，在后面我们就可以统计两个节点共同的父节点
        HashMap<Node, Node> fatherMap = new HashMap<>();
        // 用这个方法统计所有节点的父节点
        process(head, fatherMap);
        // 将头节点也存放在里面去
        fatherMap.put(head, head);
        // 用一个set来存放一个节点的父节点，从低往上循环
        HashSet<Node> set1 = new HashSet();
        // 用这个cur变量去遍历这循环
        Node cur = o1;
        // 这个循环什么时候停止 就当我取到当前hashmap的key是本身的时候停止 就证明已经在顶部了
        while (!(fatherMap.get(cur) == cur)) {
            set1.add(cur);
            cur = fatherMap.get(cur);
        }
        //这样set1当中就已经存放了 cur当中的所有父节点了，但是还没有头节点的。所有我们需要加上去
        set1.add(head);

        // 现在就需要去循环o2当中所有的父节点 如果在o2的遍历过程中。发现了第一个和set1当中的值相同，那么这个值就是最低的共同祖先
        Node cur2 = o2;
        while (!(fatherMap.get(cur2) == cur2)) {
            if (set1.contains(cur2)) {
                return cur2;
            }
            cur2 = fatherMap.get(cur2);
        }
        return head;
    }
    public static void process(Node head, HashMap<Node, Node> fatherMap) {

        if (head == null) {
            return;
        }

        fatherMap.put(head.left, head);
        fatherMap.put(head.right, head);
        process(head.left, fatherMap);
        process(head.right, fatherMap);
    }


}
